/**
 * 
 */
package combinatorics;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Michael
 *
 */
public class PrintAllSubsets {

	
	public static void allSubsetsIterative(int[] s) {
		int n = 1 << s.length; // number of subset
		
		for (int i = 0; i < n; ++i) {
			// use each bit in i to determine whether to print the
			// corresponding number in s
			for (int shift = 0; shift < s.length; ++shift) {
				if ( ((i >> shift) & 1) == 1 ) { // check each bit in i
					System.out.printf("%d ", s[shift]);
				}
			}
			System.out.println();
		}
	}
	
	public static void allSubsetsRecursive(int[] s, int index, boolean[] output) {
		if (s.length == index) {
			for (int i = 0; i < s.length; ++i) {
				if (output[i])
					System.out.printf("%d ", s[i]);
			}
			System.out.println();
		}
		else {
			output[index] = false;
			allSubsetsRecursive(s, index + 1, output);
			output[index] = true;
			allSubsetsRecursive(s, index + 1, output);
		}
	}

	public static void allSubsetsRecursive(int[] a, int index, StringBuilder sb) {
		if (a.length == index) {
			System.out.println(sb.toString());
		}
		else {
			allSubsetsRecursive(a, index + 1, sb);
			allSubsetsRecursive(a, index + 1, sb.append(a[index]));
			sb.setLength(sb.length() - 1);
		}
	}
	
	public static void allSubsetsRecursive(int[] a, int index, String s) {
		if (a.length == index) {
			System.out.printf("%s\n", s);
		}
		else {
			allSubsetsRecursive(a, index + 1, s);
			allSubsetsRecursive(a, index + 1, s + a[index]);
		}
	}
	
	public static void allSubsetsWithoutDuplicates(int[] s) {
		Arrays.sort(s);
		allSubsetsWithoutDuplicates(s, 0, new ArrayList<Integer>());
	}
	
	public static void allSubsetsWithoutDuplicates(int[] s, int index,
			List<Integer> l) {
		if (s.length == index) {
			for (int i : l) {
				System.out.printf("%d ", i);
			}
			System.out.println();
		}
		else {
			int count = 0;
			for (int i = index; i < s.length && s[i] == s[index]; ++i) {
				count++;
			}
			l.add(s[index]);
			allSubsetsWithoutDuplicates(s, index + count, l);
			l.remove(l.size() - 1);
			allSubsetsWithoutDuplicates(s, index + count, l);
		}
	}
	
	public static void allSubsetsWithoutOutputDuplicates(int[] s) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i : s) {
			if (map.containsKey(i)) {
				map.put(i, map.get(i) + 1);
			}
			else {
				map.put(i, 1);
			}
		}
		Integer[] keys = map.keySet().toArray(new Integer[0]);
		allSubsetsWithoutOutputDuplicatesHelper(map, keys, 0, new StringBuilder());
	}
	
	public static void allSubsetsWithoutOutputDuplicatesHelper(Map<Integer, Integer> counts, Integer[] keys, int index, StringBuilder sb) {
		if (counts.size() == index) {
			System.out.printf("%s\n", sb.toString());
		}
		else {
			int key = keys[index];
			for (int i = 0, count = counts.get(key); i <= count; ++i) {
				for (int j = 0; j < i; ++j) {
					sb.append(key);
				}
				allSubsetsWithoutOutputDuplicatesHelper(counts, keys, index + 1, sb);
				sb.setLength(sb.length() - i);
			}
		}
	}
	
	public static void allSubsetsWithoutOutputDuplicatesHelper(Map<Integer, Integer> counts, Integer[] keys, int index, String s) {
		if (index == counts.size()) {
			System.out.printf("%s\n", s);
		}
		else {
			int key = keys[index];
			for (int i = 0, count = counts.get(key); i <= count; ++i) {
				StringBuilder sb = new StringBuilder();
				for (int j = 0; j < i; ++j) {
					sb.append(key);
				}
				allSubsetsWithoutOutputDuplicatesHelper(counts, keys, index + 1, s + sb.toString());
			}
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] set = new int[] { 1, 1, 2 };
		boolean[] output = new boolean[] {false, false, false, false};
		//allSubsetsIterative(set);
		//allSubsetsRecursive(set, 0, output);
		//allSubsetsRecursive(set, 0, new StringBuilder());
		//allSubsetsRecursive(set, 0, "");
		allSubsetsWithoutOutputDuplicates(set);
	}
	
	/**
	 * 
	 */
	public PrintAllSubsets() {
		// TODO Auto-generated constructor stub
	}

}
